import heapq


class KthLargest(object):

    def __init__(self, k, nums):
        """
        :type k: int
        :type nums: List[int]
        """
        self.k = k
        self.stack = nums[:k]
        heapq.heapify(self.stack)
        for i in range(k, len(nums)):
            if nums[i] > self.stack[0]:
                heapq.heapreplace(self.stack,  nums[i])

    def add(self, val):
        """
        :type val: int
        :rtype: int
        """
        if len(self.stack) < self.k:
            heapq.heappush(self.stack, val)
            return self.stack[0]
        else:
            if val > self.stack[0]:
                heapq.heapreplace(self.stack, val)
            return self.stack[0]
